package main.leetcode.offer.firstround.from51to68;

import main.datastruc.ListNode;

/**
 * 71.链表中环的入口节点
 *
 * <p>给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
 */
public class ex71 {
    //    private HashSet<ListNode> set = new HashSet<>();

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;
        System.out.println(new ex71().hasCycle(node3));
    }

    /** set */
    //    public ListNode entryNodeOfLoop(ListNode head) {
    //		if (head == null || !set.add(head)) {
    //			return head;
    //		}
    //		return entryNodeOfLoop(head.next);
    //	}

    /** 快慢指针 */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            if (slow == fast) {
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }
}
